import java.nio.file.attribute.UserPrincipal;

public class HashBunk {
    //手动实现一个hash表
    public static class Node{
        public int val;
        public int key;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] arry;//初始化容量为10
    public int UsedSize=0;
    public double load_factpr=0.75;//Java内置负载因子默认值为0.75

    public HashBunk(){
        arry= new Node[10];
    }

    public void put(int key, int val){
        //根据key的值找位置：例如:4%10=4,4就是当前位置
        //index位置是一个链表，若当前位置存在key,若存在就更新value值，不存在就插入即可
        int index=key%arry.length;
        //遍历链表进行插入
        Node cur=arry[index];
        while(cur!=null){
            if(cur.key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //到这里说明不存在，那么就进行新的值插入
        Node newNode=new Node(key,val);
        newNode.next=arry[index];
        arry[index]=newNode;
        UsedSize++;
        //还需处理负载因子的问题（即扩容）
        if(doFactor()>=load_factpr){
            grow();//进行扩容
        }
    }

    private void grow() {
        //这里需要注意，这里扩容并非直接使用copyof,需要把原数组的每一个节点重新hash到新的桶位置
        Node[] newArray=new Node[2*arry.length];
        for(int i=0;i<arry.length;i++){//遍历原来的数组
            //每一个下标都是一个链表
            Node cur=arry[i];
            while(cur!=null){
                int newindex=cur.key%arry.length;//确定当前key在新的桶中的位置
                Node Nodenext=cur.next;
                cur.next=newArray[newindex];
                newArray[newindex]=cur;
                cur=Nodenext;
            }
        }
        arry=newArray;
    }

    private double doFactor() {
        return UsedSize*1.0/arry.length;
    }

    public int get(int key) {
        int index=key%arry.length;
        Node cur=arry[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.val;//找到返回value即可
            }
            cur=cur.next;
        }
        return -1;//没找到返回-1即可
    }
}
